﻿/*
    http://kblog.popekim.com/2010/07/3.html
        01. Pointer 
        02. 비트 연산자
                http://whiteheim.tistory.com/47
        03. virtual keyword 의 의미 
        04. 다형성 ( polymorphism, polimorphism )
                A function having the same name, but different type or number of arguments.
                Ex : The below functions can be members of the same class.
                    void calc(int a, int b);
                    void calc(float a, float b);
        05. 상속 
        06. 추상 클래스 ( abstract class ) 
                Abstraction refers to the act of representing essential features without including the background details.
                That means abstraction is separating the logical properties from implementation details.
                For example driving the car is a logical property and design of the engine is the implementation detail.
        07. static keyword 의 의미 
        08. const keyword 의 의미 
        09. pointer 와 reference 의 차이 
        10. malloc/fee 와 new/delete 의 차이 
        11. 일반 
        12. 2 진수 다루기 
        13. 일반적인 논리력 
        14. 기타 해당직에 관련된 질문들 
        15. C의 atoi 함수를 구현해 볼 것 
        16. C의 strlen 함수를 구현해 볼 것
        17. virtual void foo() = 0; 의 의미는 무엇인가 (클래스 선언 안에서)
        18. virtual 함수란 무엇인가
                A derived class may use the redefinition for a function from the base class.
                To be possible, need to declare that function virtual in the base class.
        19. polymorphism이란 무엇인가 
        20. virtual 함수를 이용하는 간단한 클래스들을 구현해 볼 것 
        21. bool isPowerOfTwo(unsigned int num) - num이 2의 승수인지를 판단하는 함수를 구현할 것 
        22. void ReveseWordByWord(char* str) - str로 전달된 문장의 단어순서를 뒤집는 함수를 구현할 것. 예: "Dog is Cute"가 입력값이면 "Cute is Dog"이 반환값이어야 함 
        23. void swap(unsigned char a, unsigned char b) - a와 b가 8bit 숫자일때 a와 b의 값을 바꾸는 함수를 구현할것. 단 새로운 변수를 사용하면 안됨. 
        24. void foo() const; 에서 const의 의미는 무엇인가 (클래스 선언안에서)

        Encapsulation
            Part of the information can be hidden about an object.
            Encapsulation isolates the internal functionality from the rest of the application.
        
        Inheritance
            One class, called derived, can reuse the behavior of another class, known as base class.
            Methods of the base class can be extended by adding new proprieties or methods.

        Define Constructor, Default Constructor and Copy Constructor
            Constructor is used for creating and initializing an object.
            Default Constructor has no arguments and is created by default if no explicit definition is used.
            Copy Constructor is used for initializing the member variables with the values of another object of the same class.
            Important: Copy Constructor is by default called when an object is returned from a function or when the object is passed as argument by value.

        inline function
            It's a directive for the compiler which says that the code of the function is used every time we have a call.
            In this way are avoided the jump to the function routine and return. Inline function needs to be small.

        public, private and protected access specifies
            public    - data and methods can be accessed outside of the object class.
            protected - data and methods are available only for derived classes.
            private   - data and methods can not be accessed outside of the object class.

        Define Storage Classes and explain application domain.
            register - tell to the compiler for use a CPU register for fast aceess for that variable.
            auto     - it's a variable created and initialized when it is defined. It is not visible outside of the block.
            static   - defined inside of the function retain its value between calls. Always is initialized with 0. Defined as global in a file is visible on for the functions from that file.
            extern   - the definition of the variable is in another file.

        Define the Storage Qualifiers
            const    - define a variable that can not change its value along the program execution.
            volatile - define a variable that can be changed indirectly. An example can be a counter register that is updated by hardware.
            mutuable - a member of a structure or object can be changed even if the structure, for example is declared const:
                struct complex {mutuable int x; int y;};
                const complex Mycomplex = {1, 2};
                Mycomplex.x = 3; // correct

        virtual destructor
            If an object (with a non-virtual destructor) is destroyed explicitly by applying the delete operator
            to a base-class pointer to the object, the base-class destructor function (matching the pointer type) is called on the object.

        scope resolution operator
            A scope resolution operator (::) can be used to define the member functions of a class outside the class.
            Most generally a scope resolution operator is required when a data member is redefined by a derived class,
            or an overriden method of the derived class wants to call the base class version of the same method.            

    Blizzard Quiz
        Problem: Write a Checkers subset  
        Write a program that can play a legal game of Checkers Lite.
        The computer makes legal moves (random legal moves are acceptable for this checkers "AI").
        The human player is not allowed to make illegal moves.
        Checkers Lite is the same as American Checkers (also known as English draughts)
            except there is no promotion to king by moving a piece to the last rank (therefore stalemate is possible).
        Pieces move along diagonals, and jumps must be taken, and the board is 8 x 8.
        See http://en.wikipedia.org/wiki/American_checkers if you need a refresher on the rules.
        Your program should show the game board after each move.
        If there are no legal moves, or one side is eliminated, the game is over.
        Suggested board output format as ASCII - use .
        for empty square, X for black, O for white. The  initial board layout might look like this
  
        . X . X . X . X  
        X . X . X . X .  
        . X . X . X . X  
        . . . . . . . .  
        . . . . . . . .  
        O . O . O . O .  
        . O . O . O . O  
        O . O . O . O .  
  
        This should take you between 1 and 4 hours to complete. Please present a working  program along with the amount of time you spent on the program. You can do this as a command-line program if you like (that's completely acceptable), or you can do it as a GUI program, but a working program in 4 hours or less is your mandate. 
        Note: Command-line program is  merely a suggestion to fit the 4 hour time frame. If you can get more done in time, it is certainly extra credit to exceed the minimum requirements and provide a GUI based app. 
        We prefer C++.  You are also free to use 3rd party libraries like Qt, Box2D, etc. Just make sure we can build what you deliver. I also recommend you include a working binary in your submission. A ready-to-build VS2010 solution is probably easiest, unless you use Java. In that case, just provide the source and an ant build.xml or equivalent. 
*/

#include "stdafx.h"

#include <vector>
#include <deque>
#include <map>
#include <list>

#include "atoi.h"
#include "strlen.h"
#include "isPowerOfTwo.h"
#include "ReverseWordByWord.h"
#include "Swap.h"
#include "BitwiseOperators.h"
#include "iPod.h"
#include "SimpleBinaryTree.h"
#include "Amazon.h"
#include "Singleton.h"

class Parent
{
public :
    Parent( void ) {
        std::cout << "parent" << std::endl;
    }

    virtual ~Parent( void ) {
        std::cout << "bye" << std::endl;
    }

    /*
    ~Parent( void ) {
        std::cout << "bye" << std::endl;
    }
    */
};

class Sun
    : public Parent
{
public :
    Sun( void ) {
        std::cout << "sun" << std::endl;
    }

    ~Sun( void ) {
        std::cout << "~Sun" << std::endl;
    }
};

class Daughter
{
public :
    Daughter( void ) {
        std::cout << "daughter" << std::endl;
    }
};

//=============================================================================
char * _itoa(
    int value,
    int base
) {
    if (!value)
        return "0";

    bool negative = false;
    switch (base) {
    case 10:
        if (value < 0) {
            value *= -1;
            negative = true;
        }   
        break;
    case  8:
    case 16:
        if (value <0)
            return "";
    default:
        return NULL;
    }

    static const unsigned SIZE    = sizeof(int) * 8 + 1;
    static const char *   NUMBERS = "0123456789ABCDEF";

    static char out[SIZE] = {0, };
    unsigned index = SIZE - 2;
    for (; value && index; --index, value /= base)
        out[index] = NUMBERS[value % base];

    out[index--] = negative ? '-' : '+';

    return &out[index + 1];
}

//=============================================================================
char * itoa(
    int Value,
    int Base
) {
    if (!Value)
        return "0";

    bool negative = false;
    switch (Base) {
        case 10:
            if (Value < 0) {
                Value *= -1;
                negative = true;
            }
            break;
        case 8:
        case 16:
            if (Value < 0)
                return "";
            break;
        default:
            return NULL;
    }
    
    static const unsigned SIZE    = sizeof(int) * 8 + 1;
    static const char *   NUMBERS = "0123456789ABCDEF";

    static char out[SIZE] = {0, };    
    unsigned index = SIZE - 2;
    for (; Value && index; --index, Value /= Base)
        out[index] = NUMBERS[Value % Base];

    if (negative)
        out[index--] = '-';

    return &out[index + 1];
}

/*
#02 In C++, which class methods are automatically generated by the compiler,
    under what circumstances, and what is their access protection and
    signature? Explain why you may or may not want to provide your own
    implementations of these methods.
*/
/*  
    If there is a class named Foo and no one declares methods below, complier
    will generate default public methods
    01. constructor
            Foo (void);
            Most classes have member variables and they must be initialized,
            so I always implement constructor to initialize member variables.
            Also, I want to control a class is explicit or not. For example I
            used to declare a constructor like "explicit Foo(int n); or explicit Foo(int n);
    02. destructor
            ~Foo (void);
            Like constructor, most classes have member variables and they must
            be finalized. Especially in case of a class have some dynamic
            allocated variables.
    03. copy constructor
            Foo (const Foo & foo);
            default copy constructor is shallow copy, so I always implement a
            copy constructor to control how to copy member pointer variables.
            I beleve that this is a way to write a safe and consistent code.
    04. assignment operator
            Foo & operator= (const Foo & foo);
            Like copy constructor, I always implement a assignment if it needed.
*/

/*
#04	Write a function with the following signature that, given a matrix of
    integers, builds a string with the entries of that matrix appended in
    clockwise order. For instance, the 3x4 matrix below:
        2, 3, 4, 8
        5, 7, 9, 12
        1, 0, 6, 10
    would make the string “2, 3, 4, 8, 12, 10, 6, 0, 1, 5, 7, 9”.
        void BuildStringFromMatrix(int* Matrix, int NumRows, int NumColumns, char* OutBuffer)
        {
	        // Your code goes here
        }
    OutBuffer is guaranteed to be valid and large enough to hold all of the data.
*/

//=============================================================================
void BuildStringFromMatrix(
    int *  Matrix,
    int    NumRows,
    int    NumColumns,
    char * OutBuffer
) {
    if (   !Matrix
        || !NumRows
        || !NumColumns)
        return;
    assert(OutBuffer);
    
    unsigned index = 0;
    #define APPEND_VALUE(x, y) {                                                \
        sprintf(OutBuffer + index, "%d, \0", Matrix[((x) * NumColumns) + (y)]); \
        while ('\0' != *(OutBuffer + ++index));                                 \
    }                                                                           \

    int row  = 0;
    int col  = 0;
    int rows = NumRows;
    int cols = NumColumns;
 
    while (row < rows && col < cols) {
        for (int i = col; i < cols; ++i)
            APPEND_VALUE(row, i);
        row++;
 
        for (int i = row; i < rows; ++i)
            APPEND_VALUE(i, cols - 1);
        cols--;
 
        if (row < rows) {
            for (int i = cols - 1; i >= col; --i)
                APPEND_VALUE(rows - 1, i);
            rows--;
        }
 
        if (col < cols) {
            for (int i = rows - 1; i >= row; --i)
                APPEND_VALUE(i, col);
            col++;
        }
    }

    while (',' != *(OutBuffer + --index));
    OutBuffer[index] = '\0';
}

/****************************************************************************
* 
*   main
* 
***/
int _tmain(
    int      argc,
    _TCHAR * argv[]
) {
    _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
    
    Parent * parent = new Sun;
    delete parent;

    Sun * sun = new Sun;
    delete sun;

    {
        /*
        vector< unsigned int > values;
        values.push_back( 1 );
        values.push_back( 2 );
        values.push_back( 3 );
        vector< vector< unsigned int > > combinations;
        quiz::GernerateCombinations(
            values,
            3,
            combinations
        );
        */
    }
    
    {
        const char * path = "/home/abc/.././def/./ghi/../.";
        string dest;
        quiz::ConvertUnixPathToAbsolutePath(
            path,
            dest
        );
    }
    
    {
        const unsigned int size          = 10;
              int          array[ size ] = { 6, 7, 8, 8, 2, 236, 4, 94, 234, -123 };
              int          second        = 0;
        if( !quiz::Get2ndLargestElement(
                array,
                size,
                second
        ) )
            assert( false );
    }
    
    {
        struct Item {
            unsigned int data;

            Item(
                unsigned int data
            )   : data( data )
            {}

            static bool Compare(
                const Item & i1,
                const Item & i2
            ) {
                return i1.data < i2.data;
            }
        };


        std::list< Item * > items;
        items.push_back( new Item( 4 ) );
        items.push_back( new Item( 2 ) );
        items.push_back( new Item( 6 ) );
        items.push_back( new Item( 5 ) );

        /*
        std::sort( items.begin(), items.end(), Item::Compare );
        */
        
        auto it  = items.begin();
        auto end = items.end();
        for( ; it != end; it++ ) {
            Item * item = *it;
            std::cout << item->data << " ";
        }
        std::cout << std::endl;
    }
    
    {
        quiz::SimpleBinaryTree tree;
        for( unsigned int i = 0; i < 10; i++ )
            tree.Insert( i + 1 );

        unsigned int result = 0;
        quiz::Find3rdElement(
            tree.GetRoot(),
            8,
            result
        );
    }

    {
        class Test
            : public Singleton< Test >
        {
        
        public :

             Test() {}
            ~Test() {}

            void print( void ) {
                std::cout << "test" << std::endl;
            }
        };

        Test::GetInstance().print();
    }
    
    {
        unsigned int array[] = { 2, 1, 2, 4, 3, 1, 5, 1 };
        std::vector< unsigned int > result;
        quiz::GenerateDuplicatesArray( array, 8, result );
    }
    
    {
        quiz::SimpleBinaryTree tree;
        for( unsigned int i = 0; i < 4; i++ )
            tree.Insert( i + 1 );

        quiz::ReplaceAllNodes( tree.GetRoot() );
        std::vector< unsigned int > list;
        quiz::TreeToList( tree.GetRoot(), list );
        std::sort( list.begin(), list.end() );
    }
    
    {
        quiz::decimal_to_roman( 89 );
    }

    {
        quiz::MusicStore store;
        const char * song = NULL;
        store.play( "Guns N Roses", "Welcome To the Jungle" ); 
        song = store.topSong( "Guns N Roses" ); // "Welcome To the Jungle" 
        store.play( "Guns N Roses", "Sweet Child of Mine" ); 
        song = store.topSong( "Guns N Roses" ); // "Welcome To the Jungle" 
        store.play( "Guns N Roses", "Welcome To the Jungle" ); 
        song = store.topSong( "Guns N Roses" ); // "Sweet Child of Mine"

    }
    
    {
        quiz::SimpleBinaryTree tree;
        for( unsigned int i = 0; i < 20; i++ )
            tree.Insert( i + 1 );

        quiz::Node * root = tree.GetRoot();
        quiz::NodeWeight weight = quiz::FindLightestNode( root );

        printf(
            "data : %d, weight : %d\r\n",
            weight.node->data,
            weight.weight
        );
    }
    
    {
        unsigned int arr[] = {
            4, 5, 2, 25
        };
        quiz::GetNextGreatestNumber(
            arr,
            4
        );
    }
    
    {
        const unsigned int size = 6;
        int array[ size ] = { 0, };
        for( unsigned int i = 0; i < size; i++ )
            array[ i ] = i + 1;

        std::vector< int > result;

        quiz::GenerateSubSet(
            array,
            size,
            2,
            result
        );

        for( unsigned int i = 0; i < result.size(); i += 2 )
            printf( "{ %d, %d }, ", result[ i ], result[ i + 1 ] );
        std::cout << std::endl;
    }
    
    {
        quiz::RequestHandler handler;
        handler.AddBuilding( 10 );
        handler.AddBuilding( 10 );
        handler.AddBuilding( 10 );
        handler.Request();
        handler.Request();
        handler.Request();
    }

    {
        char test[] = "AGCEGDHYR";
        quiz::SortUniqueAsciiCharacterSet(
            test,
            strlen( test )
        );
    }
    
    {
        int next = 0;
        if( quiz::GetNextGreatestNumber( 4765, next ) )
            assert( next == 5467 );
        if( quiz::GetNextGreatestNumber( 8135, next ) )
            assert( next == 8153 );
        if( quiz::GetNextGreatestNumber( 838765, next ) )
            assert( next == 853678 );
    }
    
    {
        quiz::ReadBigBinaryFile();
    }
    
    {
        quiz::Queue queue( 10 );
        for( unsigned int i = 0; i < 10; i++ )
            queue.Push( i + 1 );

        unsigned int val = 0;
        for( unsigned int i = 10; i > 0; i-- ) {
            queue.Pop( val );
            queue.Push( i );
        }
        for( unsigned int i = 0; i < 10; i++ ) {
            queue.Pop( val );
            queue.Push( i );
        }

        unsigned int count = queue.GetCount();
        for( unsigned int i = 0; i < count; i++ ) {
            unsigned int val = 0;
            if( queue.Pop( val ) )
                std::cout << val << " | ";
        }
        std::cout << std::endl;
    }
    
    {
        const char * result = quiz::FindFirstRepeat(
            "abcxrrxabcrr",
            3
        );
        std::cout << result << std::endl;
    }

     
    quiz::SimpleBinaryTree tree;
    tree.Insert( 10 );
    tree.Insert( 5  );
    tree.Insert( 20 );
    tree.Insert( 7  );
    tree.Insert( 2  );
    tree.Insert( 18 );
    tree.Trim( 7, 18 );
     
    //CheckersLite checkers;
    //checkers.Play();
    
    
    //===========================================================================
    // 02. 비트 연산자
    //===========================================================================
    {
        const unsigned int size = 10;
        for( unsigned int i = 0; i < size; i++ )
            std::cout << i
                      << " = "
                      << quiz::IntergerToBinaryString( i )
                      << std::endl;
    }

    //===========================================================================
    // 10. malloc/fee 와 new/delete 의 차이
    //===========================================================================
    /*
        new/delete
            new calls an objects constructor and delete calls the destructor.
            the global new and delete *can* be overridden

        malloc/free
            only allocate and free the memory, without executing any code of the object.
            malloc/free *cannot* be overridden.
    */
    

    //===========================================================================
    // 15. C의 atoi 함수를 구현해 볼 것
    //===========================================================================
    {    
        const unsigned int size = 4;
        const char * numbers[ size ] = {
            " 321", "-123", " +12", "ABCD"
        };
        for( unsigned int i = 0; i < size; i++ )
            if( quiz::atoi( numbers[ i ] ) != atoi( numbers[ i ] ) )
                assert( false );
    }

    //===========================================================================
    // 16. C의 strlen 함수를 구현해 볼 것
    //===========================================================================
    {
        const unsigned int size = 4;
        const char * strings[ size ] = {
            " A ", "ABC DEF", "", "123123"
        };
        for( unsigned int i = 0; i < size; i++ )
            if( quiz::strlen( strings[ i ] ) != strlen( strings[ i ] ) )
                assert( false );
    }

    //===========================================================================
    // 21. bool isPowerOfTwo(unsigned int num)
    //===========================================================================    
    {
        const unsigned int size = 10;
              unsigned int val  = 1;
        for( unsigned int i = 0; i < size; i++ )
        {
            val *= 2;
            if( !quiz::IsPowerOfTwo( val ) )
                assert( false );
        }

        unsigned int vals[] = { 1, 3, 6, 1021, 0 };
        for( unsigned int i = 0; vals[ i ]; i++ )
            if( quiz::IsPowerOfTwo( vals[ i ] ) )
                assert( false );

    }

    //===========================================================================
    // 22. void ReveseWordByWord(char* str) - str로 전달된 문장의 단어순서를 뒤집는 함수를
    //     구현할 것. 예: "Dog is Cute"가 입력값이면 "Cute is Dog"이 반환값이어야 함 
    //===========================================================================    
    {
        char b[] = "ABC";
        char * a = "ABC";
        
        b[ 0 ] = 'D';
        // a[ 0 ] = 'D';
        
        
        const unsigned int size = 3;
        char * string[ size ] = {
            "I am a boy",
            " I am a boy ",
            "Iamaboy"
        };
        char * reversed[ size ] = {
            "boy a am I",
            " boy a am I ",
            "Iamaboy"
        };
        for( unsigned int i = 0; i < size; i++ )
        {
            size_t size = quiz::strlen( string[ i ] );
            char * src  = new char[ size + 1 ];
            strncpy_s( src, size + 1, string[ i ], size );
            src[ size ] = '\0';

            // quiz::reverse_word_inplace( src );
            // quiz::reverse_word_inplace( src );
            
            quiz::ReverseWordByWord( src );
            if( strncmp(
                    src,
                    reversed[ i ],
                    strlen( string[ i ]
            ) ) )
                assert( false );

            delete [] src;
            src = NULL;
        }
    }

    //===========================================================================
    // 23. void swap(unsigned char a, unsigned char b) - a와 b가 8bit 숫자일때 a와
    //     b의 값을 바꾸는 함수를 구현할것. 단 새로운 변수를 사용하면 안됨. 
    //===========================================================================
    {
        char n = 'A';
        char m = 'B';
        quiz::swap( n, m );
        if( n != 'B' || m != 'A' )
            assert( false );
    }

    class A {
    public:
        A (void) {
            std::cout << "A" << std::endl;
        }

        ~A (void) {
            std::cout << "~A" << std::endl;
        }
    };
    
    {   std::vector<A *> a;
        for (unsigned i = 0; i < 10; ++i)    
            a.push_back(new A());

        auto it  = a.begin();
        auto end = a.end();
        for (; it != end; ++it) {
            delete *it;
        }
    }

    /*  Group Query
        Sub Query
        Outer Join
    */
        
    
    
    _CrtDumpMemoryLeaks();
    
    return 0;
}